{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Sum of Matrix After Queries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #hash-table"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #哈希表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: matrixSumQueries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #查询后矩阵的和"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;和一个下标从 <strong>0</strong>&nbsp;开始的 <strong>二维数组</strong>&nbsp;<code>queries</code>&nbsp;，其中&nbsp;<code>queries[i] = [type<sub>i</sub>, index<sub>i</sub>, val<sub>i</sub>]</code>&nbsp;。</p>\n",
    "\n",
    "<p>一开始，给你一个下标从 <strong>0</strong>&nbsp;开始的&nbsp;<code>n x n</code>&nbsp;矩阵，所有元素均为 <code>0</code>&nbsp;。每一个查询，你需要执行以下操作之一：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>如果&nbsp;<code>type<sub>i</sub> == 0</code>&nbsp;，将第&nbsp;<code>index<sub>i</sub></code>&nbsp;行的元素全部修改为&nbsp;<code>val<sub>i</sub></code>&nbsp;，覆盖任何之前的值。</li>\n",
    "\t<li>如果&nbsp;<code>type<sub>i</sub> == 1</code>&nbsp;，将第&nbsp;<code>index<sub>i</sub></code>&nbsp;列的元素全部修改为 <code>val<sub>i</sub></code>&nbsp;，覆盖任何之前的值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>请你执行完所有查询以后，返回矩阵中所有整数的和。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/11/exm1.png\" style=\"width: 681px; height: 161px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]\n",
    "<b>输出：</b>23\n",
    "<b>解释：</b>上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩阵元素之和为 23 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/05/11/exm2.png\" style=\"width: 681px; height: 331px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]\n",
    "<b>输出：</b>17\n",
    "<b>解释：</b>上图展示了每一个查询操作之后的矩阵。所有操作执行完以后，矩阵元素之和为 17 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= queries.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>queries[i].length == 3</code></li>\n",
    "\t<li><code>0 &lt;= type<sub>i</sub> &lt;= 1</code></li>\n",
    "\t<li><code>0 &lt;= index<sub>i</sub>&nbsp;&lt; n</code></li>\n",
    "\t<li><code>0 &lt;= val<sub>i</sub> &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [sum-of-matrix-after-queries](https://leetcode.cn/problems/sum-of-matrix-after-queries/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [sum-of-matrix-after-queries](https://leetcode.cn/problems/sum-of-matrix-after-queries/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['3\\n[[0,0,1],[1,2,2],[0,2,3],[1,0,4]]', '3\\n[[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        result = 0\n",
    "        remainCol = set(range(n))\n",
    "        remainRow = set(range(n))\n",
    "        for tp, idx, val in queries[::-1]:\n",
    "            \n",
    "            if tp == 0 and idx in remainRow:\n",
    "                remainRow.remove(idx)\n",
    "                \n",
    "                result += val * len(remainCol)\n",
    "            elif tp == 1 and idx in remainCol:\n",
    "                remainCol.remove(idx)\n",
    "                \n",
    "                result += val * len(remainRow)\n",
    "            if not remainCol or not remainRow:\n",
    "                return result\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        Sr, Sc = set(), set()\n",
    "        res = 0\n",
    "        while queries:\n",
    "            t, i, v = queries.pop()\n",
    "            if t == 0:\n",
    "                if i in Sr:\n",
    "                    continue\n",
    "                Sr.add(i)\n",
    "                res += (n - len(Sc)) * v\n",
    "            else:\n",
    "                if i in Sc:\n",
    "                    continue\n",
    "                Sc.add(i)\n",
    "                res += (n - len(Sr)) * v\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        #值覆盖问题 倒着搞\n",
    "        ans=0\n",
    "        row=set()\n",
    "        col=set()\n",
    "        q=len(queries)\n",
    "        for i in range(q-1,-1,-1) :\n",
    "            x=queries[i]\n",
    "            op,a,b=x[0],x[1],x[2]\n",
    "            #print(op,a,b)\n",
    "            if op==0 and a not in row :\n",
    "                ans+=b*(n-len(col))\n",
    "                row.add(a)\n",
    "            if op==1 and a not in col :\n",
    "                ans+=b*(n-len(row))\n",
    "                col.add(a)\n",
    "            #print(ans)\n",
    "        return ans\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        \n",
    "        # ans = 0\n",
    "        # vis = [set(), set()]\n",
    "        # for type, index, val in reversed(queries):\n",
    "        #     if index not in vis[type]: #后面(>i)没有对这一行/列的操作\n",
    "        #         ans += (n - len(vis[type ^ 1])) * val\n",
    "        #         vis[type].add(index) # 标记操作过\n",
    "        # return ans\n",
    "        # 模拟\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for t, index, val in reversed(queries):\n",
    "            if index not in vis[t]: \n",
    "                ans += (n - len(vis[t ^ 1])) * val \n",
    "                vis[t].add(index) \n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        # m = len(queries)\n",
    "        # r = list(range(n))\n",
    "        # c = list(range(n))\n",
    "        # ans = 0\n",
    "        # for type, index, val in queries[::-1]:\n",
    "        #     if type == 0:\n",
    "        #         if index in r:\n",
    "        #             ans += len(c) * val\n",
    "        #             r.remove(index)\n",
    "        #     else:\n",
    "        #         if index in c:\n",
    "        #             ans += len(r) * val\n",
    "        #             c.remove(index)\n",
    "        # return ans\n",
    "\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        col = []\n",
    "        ind = []\n",
    "        for ii in range(len(queries)-1,-1,-1):\n",
    "            type,i,val = queries[ii][0],queries[ii][1],queries[ii][2]\n",
    "            if type == 0:\n",
    "                if i in ind:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(col))*val\n",
    "                    ind.append(i)\n",
    "            else:\n",
    "                if i in col:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(ind))*val\n",
    "                    col.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis =[set(),set()]\n",
    "        for  type,index,val in reversed(queries):\n",
    "            if index not in vis[type]:\n",
    "                ans += (n-len(vis[type^1]))*val\n",
    "                vis[type].add(index)\n",
    "        return ans\n",
    "\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for t, i, v in reversed(queries):\n",
    "            if i not in vis[t]:\n",
    "                ans += (n - len(vis[t ^ 1])) * v\n",
    "                vis[t].add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = set()\n",
    "        col = set()\n",
    "        \n",
    "        res = 0\n",
    "        for t,idx,val in queries[::-1]:\n",
    "            # 行\n",
    "            if t == 0 and (idx not in row):\n",
    "                # 受列限制\n",
    "                res += val*(n-len(col))\n",
    "                row.add(idx)\n",
    "            # 列    \n",
    "            if t == 1 and (idx not in col):\n",
    "                # 受行限制\n",
    "                res += val*(n-len(row))\n",
    "                col.add(idx)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        cols = set(range(n))\n",
    "        rows = set(range(n))\n",
    "        res = 0\n",
    "        for t, idx, val in queries[::-1]:\n",
    "            if t == 0:\n",
    "                if idx in rows:\n",
    "                    res += len(cols) * val\n",
    "                    rows.remove(idx)\n",
    "            else:\n",
    "                if idx in cols:\n",
    "                    res += len(rows) * val\n",
    "                    cols.remove(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        hashmap_col = {} # 记录后从往前已经覆盖过的\n",
    "        hashmap_row = {}\n",
    "        col_cover, row_cover = 0, 0\n",
    "        tot = 0\n",
    "        for i in range(len(queries)-1, -1, -1):\n",
    "            t = queries[i]\n",
    "            if t[0]==1:\n",
    "                if hashmap_col.get(t[1], -1) == -1:\n",
    "                    col_cover += 1\n",
    "                    tot += ((n-row_cover)*t[2])\n",
    "                    hashmap_col[t[1]] = 1\n",
    "            else:\n",
    "                if hashmap_row.get(t[1], -1) == -1:\n",
    "                    row_cover += 1\n",
    "                    tot += (n-col_cover)*t[2]\n",
    "                    hashmap_row[t[1]] = 1\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        visited = [set(), set()]\n",
    "        res = 0\n",
    "        for t, i, v in reversed(queries):\n",
    "            if i in visited[t]: continue\n",
    "            res += v * (n - len(visited[1-t]))\n",
    "            visited[t].add(i)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        s = [set(), set()]\n",
    "        ret = 0\n",
    "        for i in range(len(queries) - 1, -1, -1):\n",
    "            t, idx, v = queries[i]\n",
    "            if idx in s[t]:\n",
    "                continue\n",
    "            s[t].add(idx)\n",
    "            ret += (n - len(s[t ^ 1])) * v\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        vis = [set(), set()]\n",
    "        ans = 0\n",
    "        for t, i, v in reversed(queries):\n",
    "            if i not in vis[t]:\n",
    "                ans += (n - len(vis[t^1])) * v \n",
    "                vis[t].add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for t, idx, val in reversed(queries):\n",
    "            if idx not in vis[t]:\n",
    "                ans += (n - len(vis[t ^ 1])) * val\n",
    "                vis[t].add(idx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for tp, index, val in reversed(queries):\n",
    "            if index not in vis[tp]:\n",
    "                ans += (n - len(vis[tp^1])) * val\n",
    "                vis[tp].add(index)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        temp = [set(),set()]\n",
    "        for type,idx,val in queries[::-1]:\n",
    "            if idx not in temp[type]:\n",
    "                ans += (n - len(temp[type ^ 1])) * val\n",
    "                temp[type].add(idx)\n",
    "        return ans               "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:\n",
    "                ans += (n - len(vis[type^1])) * val\n",
    "            vis[type].add(index)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:\n",
    "                # 这一行/列还剩下n-len(vis[type^1])个可以填入的格子\n",
    "                ans += (n - len(vis[type^1])) * val\n",
    "                vis[type].add(index)\n",
    "\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "\n",
    "        rc=cc=n\n",
    "        row=set()\n",
    "        col=set()\n",
    "        res=0\n",
    "        for t,idx,val in queries[::-1]:\n",
    "            if t==0 and idx not in row:\n",
    "                res+=cc*val\n",
    "                rc-=1\n",
    "                row.add(idx)\n",
    "            elif t==1 and idx not in col:\n",
    "                res+=rc*val\n",
    "                cc-=1\n",
    "                col.add(idx)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        queriesList = []\n",
    "        c = set()\n",
    "        r = set()\n",
    "        length = len(queries)\n",
    "        lost = 0\n",
    "        res=0\n",
    "        for i in range(length-1,-1,-1):\n",
    "            typeI,indexI,valI = queries[i]\n",
    "            res+=n*valI\n",
    "            if typeI == 1:\n",
    "                if indexI in c:\n",
    "                    lost+=n*valI\n",
    "                else:\n",
    "                    lost+=len(r)*valI\n",
    "                c.add(indexI)\n",
    "            else:\n",
    "                if indexI in r:\n",
    "                    lost+=n*valI\n",
    "                else:\n",
    "                    lost+=len(c)*valI\n",
    "                r.add(indexI)\n",
    "        print(res,lost)\n",
    "        return res-lost"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)\n",
    "        return ans;"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        hashmap_col = {} # 记录后从往前已经覆盖过的\n",
    "        hashmap_row = {}\n",
    "        col_cover, row_cover = 0, 0\n",
    "        tot = 0\n",
    "        for i in range(len(queries)-1, -1, -1):\n",
    "            t = queries[i]\n",
    "            if t[0]==1:\n",
    "                if hashmap_col.get(t[1], -1) == -1:\n",
    "                    col_cover += 1\n",
    "                    tot += ((n-row_cover)*t[2])\n",
    "                    hashmap_col[t[1]] = 1\n",
    "            else:\n",
    "                if hashmap_row.get(t[1], -1) == -1:\n",
    "                    row_cover += 1\n",
    "                    tot += (n-col_cover)*t[2]\n",
    "                    hashmap_row[t[1]] = 1\n",
    "        return tot\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(),set()]\n",
    "        for t,i,v in queries[::-1]:\n",
    "            if i not in vis[t]:\n",
    "                ans+=(n-len(vis[t^1]))*v\n",
    "                vis[t].add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row, col = defaultdict(int), defaultdict(int)\n",
    "        rc, cc = n, n\n",
    "        res = 0\n",
    "        \n",
    "        for t, i, v in queries[::-1]:\n",
    "            if t == 0:\n",
    "                if i not in row:\n",
    "                    row[i] = v\n",
    "                    res += v * cc\n",
    "                    rc -= 1\n",
    "            else:\n",
    "                if i not in col:\n",
    "                    col[i] = v\n",
    "                    res += v * rc\n",
    "                    cc -= 1\n",
    "        return res\n",
    "                \n",
    "        \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # 倒序操作+简洁写法\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        #解题思路：\n",
    "        #逆向思维，对queries 进行倒序操作，这样已经修改过的元素不能再修改，可以避免大量重复操作\n",
    "\n",
    "        row = set()\n",
    "        col = set()\n",
    "\n",
    "        res = 0\n",
    "        for t,idx,val in queries[::-1]:\n",
    "            if t == 0 and idx not in row:\n",
    "                res += val * (n - len(col))\n",
    "                row.add(idx)\n",
    "            if t == 1 and idx not in col:\n",
    "                res += val * (n - len(row))\n",
    "                col.add(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        rows = cols = n\n",
    "        ans = 0\n",
    "        s = set()\n",
    "        for t, i, v in queries[::-1]:\n",
    "            if rows == 0 or cols == 0:\n",
    "                return ans\n",
    "            if t and (1, i) not in s:\n",
    "                ans += rows * v\n",
    "                cols -= 1\n",
    "                s.add((1, i))\n",
    "            elif t == 0 and (0, i) not in s:\n",
    "                ans += cols * v\n",
    "                rows -= 1\n",
    "                s.add((0, i))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        hang = set()\n",
    "        lie = set()\n",
    "        ans = 0\n",
    "        for i in range(len(queries)-1,-1,-1):\n",
    "            op,idx,val = queries[i][0],queries[i][1],queries[i][2]\n",
    "            if op==0 and idx not in hang:\n",
    "                ans += (n-len(lie))*val\n",
    "                hang.add(idx)\n",
    "            elif op==1 and idx not in lie:\n",
    "                ans += (n-len(hang))*val\n",
    "                lie.add(idx)\n",
    "            print(ans)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, idx, val in reversed(queries):\n",
    "            if idx not in vis[type]:\n",
    "                ans += val*(n-len(vis[1-type]))\n",
    "                vis[type].add(idx)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = set()\n",
    "        col = set()\n",
    "        ans = 0\n",
    "        for tp, index, val in reversed(queries):\n",
    "            if tp == 0 and index not in row:\n",
    "                row.add(index)\n",
    "                ans += (n-len(col))*val\n",
    "            if tp == 1 and index not in col:\n",
    "                col.add(index)\n",
    "                ans += (n-len(row))*val\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = set()\n",
    "        col = set()\n",
    "        m = len(queries)\n",
    "        ans = 0\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            t, index, v = queries[i]\n",
    "            r, c = len(row), len(col)\n",
    "            if t == 0:\n",
    "                if index not in row:\n",
    "                    row.add(index)\n",
    "                    ans += v * (n - c)\n",
    "            else:\n",
    "                if index not in col:\n",
    "                    col.add(index)\n",
    "                    ans += v * (n - r)\n",
    "            if r == n or c == n:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        row = set()\n",
    "        col = set()\n",
    "        for tp, idx, val in reversed(queries):\n",
    "            if tp == 0:\n",
    "                if idx in row:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += (n - len(col)) * val\n",
    "                \n",
    "                row.add(idx)\n",
    "            else:\n",
    "                if idx in col:\n",
    "                    pass\n",
    "                else:\n",
    "                    ans += (n - len(row)) * val\n",
    "\n",
    "                col.add(idx)    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        row = set()\n",
    "        col = set()\n",
    "        for tp, idx, val in reversed(queries):\n",
    "            if tp == 0:\n",
    "                if idx not in row:\n",
    "                    ans += (n - len(col)) * val\n",
    "                \n",
    "                row.add(idx)\n",
    "            else:\n",
    "                if idx not in col:\n",
    "                    ans += (n - len(row)) * val\n",
    "\n",
    "                col.add(idx)    \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = [[0, -1]] * n\n",
    "        col = [[0, -1]] * n\n",
    "\n",
    "        for j, (t, i, v) in enumerate(queries):\n",
    "            if t:\n",
    "                col[i] = [t, i, v, j]\n",
    "            else:\n",
    "                row[i] = [t, i, v, j]\n",
    "        #print(row, col)\n",
    "\n",
    "\n",
    "        is_q = lambda x: x[-1] != -1\n",
    "        qs = sorted(list(filter(is_q, row)) + list(filter(is_q, col)), key=lambda x: x[-1])\n",
    "        qs = map(lambda x: x[:-1], qs)\n",
    "\n",
    "        m_sum = 0\n",
    "        rs, cs = 0, 0\n",
    "        col, cset = [0] * n, set()\n",
    "        row, rset = [0] * n, set()\n",
    "        for t, i, v in qs:\n",
    "            if t:\n",
    "                cs += v - col[i]\n",
    "                m_sum += n * v - col[i] - rs\n",
    "                \n",
    "                cset.add(i)\n",
    "                if len(cset) == n:\n",
    "                    cset = set()\n",
    "                    row = col.copy()\n",
    "                    rs = cs\n",
    "            else:\n",
    "                rs += v - row[i]\n",
    "                m_sum += n * v - row[i] - cs\n",
    "\n",
    "                rset.add(i)\n",
    "                if len(rset) == n:\n",
    "                    rset = set()\n",
    "                    col = row.copy()\n",
    "                    cs = rs\n",
    "            \n",
    "        return m_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = n\n",
    "        column =n\n",
    "        nq = len(queries)\n",
    "        d = {}\n",
    "        sum = 0\n",
    "        for i in range(nq-1,-1,-1):\n",
    "            act = queries[i]\n",
    "            id = str(act[0])+str(act[1])\n",
    "            if id in d:\n",
    "                continue\n",
    "            d[id] = 0\n",
    "            if id[0] == '0':\n",
    "                row-=1\n",
    "                sum += column*act[2]\n",
    "            else:\n",
    "                column-=1\n",
    "                sum += row*act[2]\n",
    "            if row == 0 or column == 0:\n",
    "                break\n",
    "            # print(sum)\n",
    "        return sum\n",
    "{0:[6,7,0,4,5,1,2,3,5,6]}\n",
    "{1:[2,3,0,1,4,5,7,6,0,1,2]}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        res = 0\n",
    "        row, col = [True] * n, [True] * n\n",
    "        row_n, col_n = n, n\n",
    "        for t, index, val in reversed(queries):\n",
    "            if t == 0:\n",
    "                if row[index]:\n",
    "                    row[index] = False\n",
    "                    row_n -= 1\n",
    "                    res += val * col_n\n",
    "            else:\n",
    "                if col[index]:\n",
    "                    col[index] = False\n",
    "                    col_n -= 1\n",
    "                    res += val * row_n\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row = set()\n",
    "        col = set()\n",
    "        res = 0\n",
    "\n",
    "        for type, index, val in reversed(queries): \n",
    "            if type == 0:\n",
    "                if index not in row:\n",
    "                    res += (n - len(col)) * val\n",
    "                    row.add(index)\n",
    "            else:\n",
    "                if index not in col:\n",
    "                    res += (n - len(row)) * val\n",
    "                    col.add(index)\n",
    "    \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "\n",
    "        map1 = {}\n",
    "\n",
    "        m = len(queries)\n",
    "\n",
    "        row = 0\n",
    "        col = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            map1[(i,0)]=1\n",
    "            map1[(i,1)]=1\n",
    "\n",
    "        total = 0\n",
    "        for i in range(m-1,-1,-1):\n",
    "            node = queries[i]\n",
    "            if (node[1],node[0]) in map1:\n",
    "                if node[0] == 0:\n",
    "                    total += node[2]*(n-col)\n",
    "                    \n",
    "                    row +=1\n",
    "                else:\n",
    "                    total += node[2]*(n-row)\n",
    "                 \n",
    "                    col +=1\n",
    "                del map1[(node[1],node[0])]\n",
    "  \n",
    "            if not len(map1):\n",
    "                break\n",
    "\n",
    "        return total\n",
    "            \n",
    "            \n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        col = []\n",
    "        ind = []\n",
    "        for ii in range(len(queries)-1,-1,-1):\n",
    "            type,i,val = queries[ii]\n",
    "            if type == 0:\n",
    "                if i in ind:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(col))*val\n",
    "                    ind.append(i)\n",
    "            else:\n",
    "                if i in col:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(ind))*val\n",
    "                    col.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        rows = [(-1, 0) for i in range(n)]\n",
    "        cols = [(-1, 0) for i in range(n)]\n",
    "        m = len(queries)\n",
    "        for i in range(m):\n",
    "            t, j, v = queries[i]\n",
    "            \n",
    "            if t == 0:\n",
    "                rows[j] = (i, v)\n",
    "            else:\n",
    "                cols[j] = (i, v)\n",
    "        \n",
    "        \n",
    "        rows.sort()\n",
    "        rs = [0]\n",
    "        for i in range(n):\n",
    "            rs.append(rs[-1] + rows[i][1])\n",
    "        \n",
    "        rows = [i[0] for i in rows]\n",
    "        \n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            index = bisect.bisect_right(rows, cols[i][0])\n",
    "            s += rs[-1] - rs[index] + index * cols[i][1]\n",
    "        return s\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        col = []\n",
    "        ind = []\n",
    "        for type,i,val in queries[::-1]:\n",
    "            if type == 0:\n",
    "                if i in ind:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(col))*val\n",
    "                    ind.append(i)\n",
    "            else:\n",
    "                if i in col:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(ind))*val\n",
    "                    col.append(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for t, i, v in reversed(queries):\n",
    "            if t == 0:\n",
    "                if i not in vis[t]:\n",
    "                    vis[t].add(i)\n",
    "                    ans += (n - len(vis[1])) * v\n",
    "            else:\n",
    "                if i not in vis[t]:\n",
    "                    vis[t].add(i)\n",
    "                    ans += (n - len(vis[0])) * v\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        column_set = set()\n",
    "        row_set = set()\n",
    "        for query in queries[::-1]:\n",
    "            if query[0] == 0:\n",
    "                set1, set2 = row_set, column_set\n",
    "            else:\n",
    "                set2, set1 = row_set, column_set\n",
    "            if query[1] not in set1:\n",
    "                set1.add(query[1])\n",
    "                ans += query[2] * (n - len(set2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        row_set = set()     # 记录操作过的行\n",
    "        col_set = set()     # 记录操作过的列\n",
    "        sum_ = 0            # 计算矩阵和\n",
    "        for k in range(len(queries) - 1, -1, -1):   # 倒序遍历\n",
    "            query = queries[k]\n",
    "            # 当前处理行且行未被处理过\n",
    "            if query[0] == 0 and query[1] not in row_set:\n",
    "                sum_ += (n - len(col_set)) * query[2]       # 这一行的元素和等于未被处理的列数 * 赋予的值\n",
    "                row_set.add(query[1])                       # 添加该行已处理\n",
    "            # 当前处理列且列未被处理过\n",
    "            if query[0] == 1 and query[1] not in col_set:\n",
    "                sum_ += (n - len(row_set)) * query[2]       # 这一列的元素和等于未被处理的行数 * 赋予的值\n",
    "                col_set.add(query[1])                       # 添加该列已处理\n",
    "        return sum_ \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        row = set()\n",
    "        col = set()\n",
    "        for type,x,y in reversed(queries):\n",
    "            if type and x not in col:\n",
    "                ans += (n-len(row))*y\n",
    "                col.add(x)\n",
    "            elif type==0 and x not in row:\n",
    "                ans += (n-len(col))*y\n",
    "                row.add(x)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        col = set()\n",
    "        ind = set()\n",
    "        for ii in range(len(queries)-1,-1,-1):\n",
    "            type,i,val = queries[ii]\n",
    "            if type == 0:\n",
    "                if i in ind:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(col))*val\n",
    "                    ind.add(i)\n",
    "            else:\n",
    "                if i in col:\n",
    "                    continue\n",
    "                else:\n",
    "                    ans += (n-len(ind))*val\n",
    "                    col.add(i)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        m = len(queries)\n",
    "        r = set()\n",
    "        c = set()\n",
    "        ans = 0\n",
    "        for type, index, val in queries[::-1]:\n",
    "            if type == 0:\n",
    "                if index not in r:\n",
    "                    ans += (n-len(c)) * val\n",
    "                    r.add(index)\n",
    "            else:\n",
    "                if index not in c:\n",
    "                    ans += (n-len(r) )* val\n",
    "                    c.add(index)\n",
    "        return ans\n",
    "\n",
    "        # ans = 0\n",
    "        # vis = [set(), set()]\n",
    "        # for type, index, val in reversed(queries):\n",
    "        #     if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "        #         # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "        #         ans += (n - len(vis[type ^ 1])) * val\n",
    "        #         vis[type].add(index)  # 标记操作过\n",
    "        # return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        rowvisited = set()\n",
    "        colvisited = set() \n",
    "        row_n = n \n",
    "        col_n = n \n",
    "        res = 0\n",
    "        for i in range(len(queries)-1, -1, -1):\n",
    "            typ, idx, val = queries[i]\n",
    "            # row\n",
    "            if typ == 0:\n",
    "                if idx not in rowvisited:\n",
    "                    res += col_n * val \n",
    "                    row_n -= 1\n",
    "                    rowvisited.add(idx)\n",
    "            # col\n",
    "            else:\n",
    "                if idx not in colvisited:\n",
    "                    res += row_n * val\n",
    "                    col_n -= 1 \n",
    "                    colvisited.add(idx)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        vis = [set(), set()]\n",
    "        for type, index, val in reversed(queries):\n",
    "            if index not in vis[type]:  # 后面（>i）没有对这一行/列的操作\n",
    "                # 这一行/列还剩下 n-len(vis[type^1]) 个可以填入的格子\n",
    "                ans += (n - len(vis[type ^ 1])) * val\n",
    "                vis[type].add(index)  # 标记操作过\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        m = len(queries)\n",
    "        r = list(range(n))\n",
    "        c = list(range(n))\n",
    "        ans = 0\n",
    "        for type, index, val in queries[::-1]:\n",
    "            if type == 0:\n",
    "                if index in r:\n",
    "                    ans += len(c) * val\n",
    "                    r.remove(index)\n",
    "            else:\n",
    "                if index in c:\n",
    "                    ans += len(r) * val\n",
    "                    c.remove(index)\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        vis = [set(), set()]\n",
    "        res = 0\n",
    "        for q in reversed(queries):\n",
    "            t, i, v = q[0], q[1], q[2]\n",
    "            # if t == 0 and row[i]:\n",
    "            #     row[i] = False\n",
    "            if i in vis[t]:\n",
    "                continue\n",
    "            res += (n-len(vis[1 - t]))*v\n",
    "            vis[t].add(i)\n",
    "        return res\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # col = [[0,0] for _ in range(n)]\n",
    "        # row = [[0,0] for _ in range(n)]\n",
    "        # # 第一个是值 第二个是上次碰他的order\n",
    "\n",
    "        # m = len(queries)\n",
    "        # ordC = [-1]*(m+1)\n",
    "        # ordR = [-1]*(m+1)\n",
    "        # # order到行/列号的映射 order o -> 第几行更新的\n",
    "\n",
    "        # # 有一个更新顺序的问题，\n",
    "        # # 某行有 row[i] 而有若干列 col[a1 ...ak]\n",
    "        # # order matters, 假如\n",
    "        # # 要覆盖行\n",
    "        # # 先计算存在值，再更新\n",
    "        # # odrR[i] 我要找所有晚于这个order的 col updates\n",
    "                \n",
    "        # \"\"\"\n",
    "        # 我需要记住order 给定一个order （当前行的上一次更新的order）我需要查询所有晚于这个order的行/列, \n",
    "        # 这有两个问题：1 如何查询/保存当前行的上一层更新 -- 只能用行index查 有一个arr index -> 上次触碰该行的order\n",
    "        # 2. 如何按照order查询晚于这个order的列 这里就需要order索引的数组了\n",
    "        \n",
    "        # \"\"\"\n",
    "        # res = 0\n",
    "        # for Ii, q in enumerate(queries):\n",
    "        #     I = Ii + 1 # 让order都从1开始\n",
    "        #     t, i, v = q[0], q[1], q[2]\n",
    "        #     if t == 0:\n",
    "        #         # 可以surfixSum优化？\n",
    "        #         tmp = row[i][0]*n\n",
    "        #         for o in range(row[i][1], I):\n",
    "        #             if ordC[o] != -1:\n",
    "        #                 tmp = tmp-row[i][0]+col[ordC[o]][0]\n",
    "        #         ##\n",
    "        #         res = res - tmp + n*v\n",
    "        #         ordR[I] = i\n",
    "        #         row[i][0], row[i][1] = v, I\n",
    "        #     else: # t == 1:\n",
    "        #         if res == 2538903:\n",
    "        #             print(q)\n",
    "        #             print(res)\n",
    "        #             print(col[0])\n",
    "        #             print(row)\n",
    "        #             print(ordR)\n",
    "\n",
    "        #         tmp = col[i][0]*n \n",
    "        #         for o in range(col[i][1], I):# 5, 18\n",
    "        #             # 在 ordC[i] 后面更新的 row\n",
    "        #             if ordR[o] != -1:\n",
    "        #                 tmp = tmp-col[i][0]+row[ordR[o]][0]\n",
    "        #                 if res == 2538903:\n",
    "        #                     print(o, ordR[o], row[5]) #row[ordR[o]])\n",
    "        #         ## \n",
    "        #         # print(ordR)\n",
    "        #         # print(tmp)\n",
    "        #         res = res - tmp + n*v\n",
    "        #         ordC[I] = i\n",
    "        #         col[i][0], col[i][1] = v, I\n",
    "        #     # print(q, res)\n",
    "            \n",
    "            \n",
    "        # return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:\n",
    "        vis=[set(),set()]\n",
    "        ans=0\n",
    "        for op,index,val in reversed(queries) :\n",
    "            if index not in vis[op] :\n",
    "                ans+=val*(n-len(vis[op^1]))\n",
    "                vis[op].add(index)\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
